在算法的分析中，语句的执行次数T(n)是一个关于n（问题规模）的一个函数。分析n的变化引起T（n）的改变，进而得到T（n）的数量级，也就是时间频率。如果存在某一个辅助函数f（n），当n趋于无穷大时，T(n)/f(n)的值为一个不为0的常数，有T(n)=O(f(n)),这就是算法的渐进时间复杂度，也就是我们常说的时间复杂度。

大O表示法：用O(f(n))来体现时间复杂度的方法被称作大O表示法； 大O推导法： O（1）叫做常数阶；O（n）叫做线性阶；O(n^2)叫做平方阶。

举一个简单的例子

}

int main() { int arr[] = { 4,5,8,9,1,2 }; int len = sizeof(arr) / sizeof(int);//通过字节计算数组大小 printArray(arr, len); InsertSort(arr, len); printArray(arr, len); return 0; }

1、当初始序列为正序时，只需要外循环n-1次，每次进行一次比较，无需移动元素。此时比较次数(C min)和移动次数(M min)达到最小值。 C min=n-1; M min=0; 此时时间复杂度为O(n). 2、初始序列为反序时，需要外循环n-1次，每次排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移i次，此时比较次数和移动次数达到最大值。 C min=1+2+3+4+……+n-1=(n-1)n/2; M min=1+2+3+……+n-1=(n-1)n/2; 此时时间复杂度为O(n^2). 3、在直接插入排序中只使用了i,j,tmp这三个辅助元素，与问题规模无关，空间复杂度为O(1)

重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故称为"冒泡排序"。